import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/1 9:57
 * @description 思路：dfs咯，从外面一层的每一个O开始遍历，对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O， 设为A
 * 最后我们遍历这个矩阵，对于每一个字母：
 * 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
 * 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = {{'X','X','X','X'}, {'X','O','O','X'}, {'X','X','O','X'}, {'X','O','X','X'}};
        solution.solve(board);
    }

    int m, n;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        // 从外面一层往里面dfs
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n-1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(board, 0, j);
            dfs(board, m-1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        // 打上标记A，说明他与边界O直接或间接相连，
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }

}
